package com.df.excel_export.graph;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.serializer.SerializerFeature;
import com.df.excel_export.common.ClassDefine;
import com.df.excel_export.front.GraphData;
import com.df.excel_export.front.GraphDataNode;
import lombok.extern.slf4j.Slf4j;

import java.io.FileWriter;
import java.io.IOException;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.function.BiFunction;
import java.util.function.Function;

/**
 * 十字链表结构的有向图
 * @param <T>
 */
@Slf4j
public class OrthogonalGraph<T> {
    public List<Vertex<T>> vertices = new ArrayList<>();//十字链表图的顶点列表，存储所有的顶点
    public int vertexCount = 0;//顶点数量
    public int edgeCount = 0;//边数量

    public boolean cycle = false;//是否有循环依赖

    public List<Vertex<T>> sorted = new ArrayList<>();//拓扑排序后

    //添加顶点
    public void  addVertex(T data) {
        for (Vertex<T> vertex : vertices) {
            if(vertex.data==data){
                return;
            }
        }
        Vertex<T> vertex = new Vertex<>();
        vertex.data = data;
        vertices.add(vertex);
    }

    //添加边
    public void addEdge(int startIndex, int endIndex) {
        if(startIndex == -1 || endIndex == -1){
            return;
        }
        //记录出边
        Vertex<T> startV = vertices.get(startIndex);
        EdgeNode out = startV.out;
        if(out==null){
            out = new EdgeNode();
            out.tailVertexIndex = startIndex;
            out.headVertexIndex = endIndex;
            startV.out = out;
        }else{
            while (out.nextOutEdgeNode!=null){
                if(out.headVertexIndex == endIndex){//边已经存在了
                    return;
                }
                out = out.nextOutEdgeNode;
            }
            if(out.headVertexIndex == endIndex){//边已经存在了
                return;
            }
            EdgeNode edgeNode = new EdgeNode();
            edgeNode.tailVertexIndex = startIndex;
            edgeNode.headVertexIndex = endIndex;
            out.nextOutEdgeNode = edgeNode;
        }
        //记录入边
        Vertex<T> endV = vertices.get(endIndex);
        EdgeNode in = endV.in;
        if(in==null){
            in = new EdgeNode();
            in.nextInEdgeNode = out;
            endV.in = in;
        }else{
            while (in.nextInEdgeNode!=null){
                if(in.headVertexIndex == endIndex){//边已经存在了
                    return;
                }
                in = in.nextInEdgeNode;
            }
            if(in.headVertexIndex == endIndex){//边已经存在了
                return;
            }
            in.nextInEdgeNode = out;
        }
        edgeCount++;
    }

    //添加边
    public void addEdge(T start, T end) {
        int startIndex = getIndex(start);
        int endIndex = getIndex(end);
        addEdge(startIndex,endIndex);
    }

    public int getIndex(T data){
        for (int i = 0; i < vertices.size(); i++) {
            if(vertices.get(i).data.equals(data)){
                return i;
            }
        }
        return -1;
    }


    public void printGraphData2File(BiFunction<Vertex<T>,GraphData,GraphDataNode> getData) {
        GraphData graphData = new GraphData();
        for (Vertex<T> vertex : vertices) {
            GraphDataNode node = getData.apply(vertex,graphData);
            graphData.nodes.add(node);
        }

        String jsonString = JSON.toJSONString(graphData, SerializerFeature.DisableCircularReferenceDetect);
        String dataRootPath = System.getProperty("user.dir");
        //TODO 检查其他文件是否存在，不存在则拷贝

        String filePath = Paths.get(dataRootPath, "depends_graph/data.js").normalize().toAbsolutePath().toString();
        log.info("数据文件："+filePath);
        try (FileWriter writer = new FileWriter(filePath)){

            writer.write("const data = "+jsonString);
            log.info("依赖数据已经写入本地文件！");
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 检测依赖循环和拓扑排序
     * 排序：遍历所有顶点，深度遍历，顶点没有出边或所有出边都遍历完后，入栈，遍历完后，依次出栈，则为排序结果，先出栈的为前驱，
     * 如果排序列表节点和图节点数不一致，则表示有环
     */
    public void checkDependCycleAndSort() {
        boolean[] flag = new boolean[vertices.size()];//标记位数组
        Stack<Integer> stack = new Stack<>();//栈
        Arrays.fill(flag,false);
        int v;
        for(v=0; v<vertices.size(); v++){	//从v=0开始遍历
            if(!flag[v]){
                DFS(v, flag,stack);
            }
        }
        //即时有环，也存储无环的排序
        sorted.clear();
        while (!stack.isEmpty()){
            sorted.add(vertices.get(stack.pop()));
        }
        if(stack.size()!=vertexCount){//有环
            cycle = true;
        }

    }

    /**
     * 深度遍历
     * @param v 当前遍历的节点
     * @param flag 标记数组
     * @param stack 排序临时栈
     */
    void DFS(int v, boolean[] flag, Stack<Integer> stack){
        flag[v] = true;	//设已访问标记
        Vertex<T> vertex = vertices.get(v);
        EdgeNode out = vertex.out;
        while (out!=null){
            if(!flag[out.headVertexIndex]){
                DFS(out.headVertexIndex,flag, stack);
            }
            out = out.nextOutEdgeNode;
        }
        //所有出边都遍历完后，才做访问顶点的操作，此处为入栈
        visit(v,stack);	//访问顶点
    }

    private void visit(int v, Stack<Integer> stack) {
        stack.push(v);
    }

    public static void main(String[] args) {
        OrthogonalGraph<String> graph = new OrthogonalGraph<>();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");
        graph.addEdge("A","B");
        graph.addEdge("A","C");
        graph.addEdge("B","D");
        graph.addEdge("C","D");
        graph.addEdge("B","E");
        graph.addEdge("D","E");
        graph.checkDependCycleAndSort();
    }

}
